Mergesort, Quicksort & Das Teile-und-Herrsche-Prinzip
IN-SA TB #028–029
Das Teile-und-Herrsche-Prinzip (Divide and Conquer)
Das Teile-und-Herrsche-Prinzip basiert darauf, ein großes Ausgangsproblem in mehrere kleine Probleme aufzuteilen, diese zu bearbeiten und anschließend die Lösungen wieder zusammenzuführen.
Großes Problem
│
▼
Aufteilen in Teilprobleme
│
├── Teilproblem 1 ──► Lösung 1
├── Teilproblem 2 ──► Lösung 2
└── Teilproblem 3 ──► Lösung 3
│
▼
Teillösungen zusammenführen
│
▼
Gesamtlösung
Mergesort ist ein typischer Algorithmus dieses Prinzips.
Mergesort
Idee
Der Mergesort ist ein rekursives Sortierverfahren:
- Das zu sortierende Feld …
- gilt als sortiert, falls es genau aus einem Element besteht.
- wird geteilt und die Teilfelder werden wieder mit Mergesort sortiert, falls mehr als ein Element enthalten ist.
- Die sortierten Teilfelder werden gemischt (to merge) und zurückgegeben.
Beispiel: [7, 5, 9, 3, 2, 8, 4, 1]
[7, 5, 9, 3, 2, 8, 4, 1]
Teilen
/ \
[7, 5, 9, 3] [2, 8, 4, 1]
Teilen Teilen
/ \ / \
[7, 5] [9, 3] [2, 8] [4, 1]
/ \ / \ / \ / \
[7] [5] [9] [3] [2] [8] [4] [1]
\ / \ / \ / \ /
[5, 7] [3, 9] [2, 8] [1, 4]
\ / \ /
[3, 5, 7, 9] [1, 2, 4, 8]
\ /
[1, 2, 3, 4, 5, 7, 8, 9]
Implementierung in Python
def mergesort(feld):
if len(feld) <= 1:
return feld # Basisfall: ein Element ist sortiert
# Teilen
mitte = len(feld) // 2
links = mergesort(feld[:mitte])
rechts = mergesort(feld[mitte:])
# Mischen (Merge)
return merge(links, rechts)
def merge(links, rechts):
ergebnis = []
i, j = 0, 0
while i < len(links) and j < len(rechts):
if links[i] <= rechts[j]:
ergebnis.append(links[i])
i += 1
else:
ergebnis.append(rechts[j])
j += 1
# Reste hinzufügen
ergebnis += links[i:]
ergebnis += rechts[j:]
return ergebnis
Laufzeit
| Fall | Laufzeit |
|---|---|
| Best Case | O(n · log n) |
| Average Case | O(n · log n) |
| Worst Case | O(n · log n) |
Warum O(n · log n)?
- Teilen: Es entstehen genau so viele Ebenen wie beim Teilen nötig → log₂(n) Ebenen
- Mischen: Auf jeder Ebene werden insgesamt n Elemente verglichen
- Insgesamt: n · log(n) Vergleiche
Mergesort ist stabil ✓
Quicksort
Idee
„Pivot" ist französisch und bedeutet „Dreh- und Angelpunkt".
Beim Quicksort wird das zu sortierende Feld in zwei Teillisten aufgeteilt. Dazu wählt man ein Pivot-Element (einfachste Wahl: das erste Element). Das Pivot-Element sitzt nach dem Partitionieren an der richtigen Position – links davon alle kleineren, rechts davon alle größeren Elemente.
Beispiel
Feld: [17, 23, 19, 1, 7, 15, 37, 93, 5]
Pivot = 17
Nach Partitionieren:
[5, 1, 7, 15] | 17 | [23, 19, 37, 93]
< 17 Pivot > 17
→ Quicksort auf linke Teilliste
→ Quicksort auf rechte Teilliste
Implementierung in Python
def quicksort(feld, l, r):
if l >= r:
return # Basisfall
pivot_index = partitioniere(feld, l, r)
quicksort(feld, l, pivot_index - 1) # linke Teilliste
quicksort(feld, pivot_index + 1, r) # rechte Teilliste
def partitioniere(feld, l, r):
pivot = feld[l]
i = l + 1
j = r
while i <= j:
while i <= j and feld[i] <= pivot:
i += 1
while i <= j and feld[j] > pivot:
j -= 1
if i < j:
feld[i], feld[j] = feld[j], feld[i]
feld[l], feld[j] = feld[j], feld[l] # Pivot an richtige Stelle
return j
Laufzeit
| Fall | Laufzeit | Wann? |
|---|---|---|
| Best Case | O(n · log n) | Pivot teilt immer genau in der Mitte |
| Average Case | O(n · log n) | Im Durchschnitt |
| Worst Case | O(n²) | Pivot ist immer das kleinste/größte Element (z.B. bereits sortiertes Feld) |
Quicksort ist instabil ✗
Vergleich: Mergesort vs. Quicksort
| Eigenschaft | Mergesort | Quicksort |
|---|---|---|
| Worst Case | O(n log n) | O(n²) |
| Average Case | O(n log n) | O(n log n) |
| Stabil? | ✓ Ja | ✗ Nein |
| Zusätzlicher Speicher | O(n) – Hilfsfeld | O(log n) – Rekursionsstack |
| Prinzip | Teilen → Mischen | Partitionieren → Teilen |
Man sagt: Mergesort ist stabil, Quicksort ist instabil.